package algorithm.dp;

public class 最大矩形和正方形 {
    // 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
    //
    // 示例:
    //
    // 输入:
    // [
    // ["1","0","1","0","0"],
    // ["1","0","1","1","1"],
    // ["1","1","1","1","1"],
    // ["1","0","0","1","0"]
    // ]
    // 输出: 6

    public int maximalRectangle(char[][] matrix) {
        int row = matrix.length;
        if (row == 0) {
            return 0;
        }
        int col = matrix[0].length;
        int[][][] edge = new int[row + 5][col + 5][2];// edge[i][j]
                                                      // 以i,j为矩形右下角的最大矩形 第三维
                                                      // 0表示宽度，1表示高度
        int maxArea = 0;
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    edge[i][j][0] = Utils.min(edge[i][j - 1][0], edge[i - 1][j][0], edge[i - 1][j - 1][0]) + 1;
                    edge[i][j][1] = Utils.min(edge[i][j - 1][1], edge[i - 1][j][1], edge[i - 1][j - 1][1]) + 1;
                    maxArea = Math.max(edge[i][j][0] * edge[i][j][1], maxArea);
                }
            }
        }
        return maxArea;
    }

    int maximalSquare(char[][] matrix) {
        /*
         * 执行用时 : 21 ms, 在Maximal Square的Java提交中击败了8.68% 的用户 内存消耗 : 50.4 MB,
         * 在Maximal Square的Java提交中击败了13.30% 的用户
         */
        int row = matrix.length;
        if (row == 0) {
            return 0;
        }
        int col = matrix[0].length;
        int[][] edge = new int[row + 5][col + 5];// edge[i][j] 以i,j为矩形右下角的最大正方形
        int maxLen = 0;
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    edge[i][j] = Utils.min(edge[i][j - 1], edge[i - 1][j], edge[i - 1][j - 1]) + 1;
                    maxLen = Math.max(edge[i][j], maxLen);
                }
            }
        }
        return maxLen * maxLen;
    }

}
